package zuosheng.stackandQueue;

import java.util.LinkedList;

/**
 * @author lj
 * @Description: 生成窗口最大值数组
 * @date 2020-11-19 11:31
 * @QQ 851477108
 */


public class GetMaxNumInWindow {
    public static void main(String[] args) {
        int[] arr = {4,3,5,4,3,3,6,7};
        int w = 3;
        int[] res = getMaxWindow(arr,w);
        for (int i : res){
            System.out.print(i+" ");
        }
    }

    public static int[] getMaxWindow(int[] arr, int w){
        if (arr == null || w < 1 || arr.length < w){
            return null;
        }
        // 共有arr.length - win + 1个窗口，即共有arr.length - win + 1个最大值
        int[] res = new int[arr.length - w + 1];
        LinkedList<Integer> qMax = new LinkedList<>();
        int index = 0;
        for (int i = 0; i < arr.length; i++){

        //如果当前双端链表中的最后一个值比arr[i]小，则将其弹出，直到找到比arr[i]大的数，将arr[i]放在其后面，
        //如果maxQueue中没有比arr[i]大的数，那就将maxQueue中的数全部弹出，arr[i]放在头部
            while (!qMax.isEmpty() && arr[qMax.peekLast()] < arr[i]){
                qMax.pollLast();
            }
            qMax.addLast(i);

            // 只有当窗口形成后才会有从双端队列头部失效一个数,即过期还是没过期
            if (qMax.peekFirst() == i - w){
                qMax.pollFirst();
            }
            // 至少有一个窗口存在时，才有max
            if (i >= w - 1){
                res[index++] = arr[qMax.peekFirst()];
            }
        }
        return res;
    }

}
